
class Solution {
public:
    int numberOfSubstrings(string s) {
        vector<int> nstr(256);
        int left = 0, right = 0, n = s.size(), ans = 0;
        for (; right < n; right++) {
            nstr[s[right]]++;
            while (nstr['a'] && nstr['b'] && nstr['c']) {
                nstr[s[left]]--;
                left++;
            }
            ans += left;
        }
        return ans;
    }
};
using ll = long long;
// bool fun(map<int,int>& mm, int k){
//     return mm.rbegin()->second >= k;
// }
class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        int mx = ranges::max(nums);
        ll left = 0, right = 0, ans = 0;
        int n = nums.size(), sum = 0;
        ;
        for (; right < n; right++) {
            k -= nums[right] == mx ? 1 : 0;
            while (k <= 0) {
                k += nums[left] == mx ? 1 : 0;

                left++;
            }
            ans += left;
        }
        return ans;
    }
};
bool fun(vector<int>& num,int k){
    for(int i = 'a';i <= 'z';i++)
        if(num[i] >= k) return true;
    return false;
}
class Solution {
public:
    int numberOfSubstrings(string s, int k) {
        vector<int> nstr(256);
        int left = 0, right = 0, n = s.size(), ans = 0;
        for (; right < n; right++) {
            nstr[s[right]]++;
            while (fun(nstr,k)) {
                nstr[s[left]]--;
                left++;
            }
            ans += left;
        }
        return ans;
    }
};

class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        int k = unordered_set<int>(nums.begin(),nums.end()).size();
        unordered_map<int,int> window;
        int left = 0, right = 0, n = nums.size(), ans = 0;
        for (; right < n; right++) {
            window[nums[right]]++;
            while (window.size() >= k) {
                window[nums[left]]--;
                if(window[nums[left]] == 0) window.erase(nums[left]);
                left++;
            }
            ans += left;
        }
        return ans;
    }
};
bool fun(map<int,int>& mm , int k){
    for(auto e = mm.begin();k>0&&e!=mm.end();e++){
        k-= (long long)(e->second - 1)*e->second/2;
    }
    return k <= 0;
}
class Solution {
public:
    long long countGood(vector<int>& nums, int k) {
        long long ans = 0;
        int left = 0,right = 0,n = nums.size();
        unordered_map<int,int> mm;
        for(;right < n;right++){
            // k -= mm[nums[right]];
            k -= mm[nums[right]]++;
            while(k <= 0){
                // mm[nums[left]]--;
                k += --mm[nums[left]];
                // if(mm[nums[left]] == 0)
                //     mm.erase(nums[left]);
                left++;
            }
            ans += left;
        }
        return ans;
    }
};
bool fun(vector<int>& mm) {
    for (int i = 0; i < 26; i++)
        if (mm[i] > 0)
            return false;
    return true;
}
class Solution {
public:
    long long validSubstringCount(string word1, string word2) {
        long long ret = 0;
        vector<int> mm(26);
        for (auto e : word2)
            ++mm[e-'a'];
        int left = 0, right = 0, n = word1.size();
        for (; right < n; right++) {
            --mm[word1[right]-'a'];
            while(fun(mm))
            {
                ++mm[word1[left] -'a'];
                ++left;
            }
            ret += left;
        }
        return ret;
    }
};